package com.leetcode.No1766;

import org.junit.Test;

import java.util.*;

public class Solution {
    int[][] prime = new int[51][51];
    public int[] getCoprimes(int[] nums, int[][] edges) {
        for (int i = 1; i <= 50; ++i) {
            for (int j = 1; j <= 50; ++j) {
                prime[i][j] = checkPrime(i, j) ? 1 : 0;
            }
        }
        prime[1][1] = 1;

        int[] father = initFather(nums.length, edges);

        int[] result = new int[nums.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = findPrime(i, nums, father);
//            if (result[i] == 63) {
//                System.out.println(nums[i] + ", " + i + ", 6363636363");
//            }
        }
        result[0] = -1;
        return result;
    }

    private int findPrime(int currentIdx, int[] nums, int[] father) {
//        String str = String.format("nums[%s]=%s -> ", currentIdx, nums[currentIdx]);
        int otherIdx = father[currentIdx];
        while (true) {
//            str = str + String.format("nums[%s]=%s -> ", otherIdx, nums[otherIdx]);
            if (prime[nums[currentIdx]][nums[otherIdx]] == 1) {
                return otherIdx;
            }
            if (otherIdx == 0) {
                break;
            }
            otherIdx = father[otherIdx];
        }
//        if (otherIdx == 63) {
//            System.out.println(str);
//        }
        return -1;
    }

    private int[] initFather(int n, int[][] edges) {
        int[] father = new int[n];
        int[] used = new int[n];
        Map<Integer, Set<Integer>> connectMap = new HashMap<>();
        for (int[] edge : edges) {
            Set<Integer> set1 = connectMap.getOrDefault(edge[0], new HashSet<>());
            set1.add(edge[1]);
            connectMap.put(edge[0], set1);

            Set<Integer> set2 = connectMap.getOrDefault(edge[1], new HashSet<>());
            set2.add(edge[0]);
            connectMap.put(edge[1], set2);
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        while (!stack.isEmpty()) {
            Integer idx = stack.pop();
            used[idx] = 1;
            Set<Integer> set = connectMap.get(idx);
            if (set == null || set.isEmpty()) {
                continue;
            }
            for (Integer x : set) {
                if (used[x] != 1) {
                    father[x] = idx;
                    stack.push(x);
                }
            }
        }

        return father;
    }

    private boolean checkPrime(int a, int b) {
        if (a == b) {
            return false; // 不是质数
        }
        int min = Math.min(a, b);
        for (int i = 2; i <= min; ++i) {
            if (a % i == 0 && b % i == 0) {
                return false; // 不是质数
            }
        }
        return true; // 是质数
    }

    @Test
    public void test() {
//        int[] nums = new int[]{2,3,3,2};
//        int[][] edges = new int[][]{{0,1},{1,2},{1,3}};

//        int[] nums = new int[]{9,16,30,23,33,35,9,47,39,46,16,38,5,49,21,44,17,1,6,37,49,15,23,46,38,9,27,3,24,1,14,17,12,23,43,38,12,4,8,17,11,18,26,22,49,14,9};
//        int[][] edges = new int[][]{{0,1},{0,2},{1,3},{1,4},{2,5},{2,6}};

//        int[] nums = new int[]{9,16,30,23,33,35,9,47,39,46,16,38,5,49,21,44,17,1,6,37,49,15,23,46,38,9,27,3,24,1,14,17,12,23,43,38,12,4,8,17,11,18,26,22,49,14,9};
//        int[][] edges = new int[][]{{17,0},{30,17},{41,30},{10,30},{13,10},{7,13},{6,7},{45,10},{2,10},{14,2},{40,14},{28,40},{29,40},{8,29},{15,29},{26,15},{23,40},{19,23},{34,19},{18,23},{42,18},{5,42},{32,5},{16,32},{35,14},{25,35},{43,25},{3,43},{36,25},{38,36},{27,38},{24,36},{31,24},{11,31},{39,24},{12,39},{20,12},{22,12},{21,39},{1,21},{33,1},{37,1},{44,37},{9,44},{46,2},{4,46}};


        int[] nums = new int[]{18,10,23,47,11,20,7,44,14,43,43,42,2,23,5,31,18,40,49,27,50,21,19,35,23,30,31,8,7,50,7,11,4,43,1,5,24,44,24,25,24,19,48,5,37,13,50,6,20,38,43,45,34,15,42,41,5,44,16,21,26,31,12,35,13,36,2,21,29,36,7,24,1,37,40,6,19,30,12,42,30,50,20,15,34,36,49,2,34,36,38,8,11,33,46,19,24,41,2,31,14,32,9,29,12,6,45,47,32,24,37,4,25,50,24,10,31,40,5,12,22,7,23,2,27,42,8,6,1,15,16,32,32,38,29,24,33,22,33,29,17};
        int[][] edges = new int[][]{{57,0},{5,57},{76,5},{85,76},{46,85},{127,85},{25,0},{114,25},{7,114},{45,114},{100,25},{122,100},{17,122},{12,17},{48,100},{40,48},{60,40},{88,48},{108,48},{10,108},{11,10},{121,11},{9,121},{109,11},{111,109},{91,109},{118,91},{53,118},{26,53},{47,26},{126,47},{133,109},{123,133},{59,123},{81,48},{31,81},{15,31},{24,15},{132,81},{119,132},{21,119},{63,81},{128,63},{73,128},{34,63},{72,34},{38,72},{97,72},{3,97},{30,3},{13,30},{80,13},{33,80},{66,80},{102,66},{8,80},{77,8},{79,77},{42,79},{19,42},{78,19},{20,78},{55,79},{37,55},{49,37},{89,49},{36,89},{83,89},{95,49},{64,95},{28,64},{32,28},{92,32},{93,92},{86,93},{39,86},{87,39},{2,87},{134,93},{135,49},{110,3},{29,110},{52,29},{136,29},{99,136},{50,99},{84,50},{56,84},{51,99},{112,51},{101,112},{41,29},{74,41},{103,74},{129,74},{6,129},{137,129},{61,29},{104,61},{131,104},{58,104},{14,58},{18,14},{138,18},{117,138},{125,138},{106,125},{120,18},{130,120},{124,130},{62,124},{82,62},{4,62},{113,4},{139,130},{1,104},{67,1},{70,1},{43,70},{96,70},{98,96},{69,98},{94,69},{115,94},{75,1},{44,75},{68,44},{16,68},{54,68},{65,68},{27,65},{71,65},{105,65},{35,105},{107,65},{116,65},{90,116},{23,90},{140,1},{22,140}};

        System.out.println(Arrays.toString(getCoprimes(nums, edges)));
    }
}
